1. Technical Field
An “Eventually Consistent Sharing Model” provides various techniques for using fork-join automata based on revision diagrams to track the forking and joining of updates or changes to versions of shared data thereby tracking updates made to replicas of the shared data, and using “cloud types” to define the structure of that data in such a way as to enable a fully automatic conflict resolution relative to the different updates.
2. Background Art
“Eventual consistency” is a well-known workaround to the fundamental problem of providing CAP (i.e., consistency, availability, and partition tolerance) to clients that perform queries and updates against shared data in a distributed system. It weakens traditional consistency guarantees (such as linearizability) in order to allow clients to perform updates against any replica of the shared data, at any time. Eventually consistent systems guarantee that all updates are eventually delivered to all replicas, and that they are applied in a consistent order.
Eventual consistency is popular with system builders. One reason is that it allows temporarily disconnected replicas to remain fully available to clients. This is particularly useful for implementing clients on mobile devices. Another reason is that it does not require updates to be immediately performed on all server replicas, thus improving scalability. In theoretical terms, the benefit of eventual consistency can be understood as its ability to delay consensus.
Existing techniques for providing eventual consistency generally use a weak consistency model that breaks with traditional approaches (e.g., serializable operations) and thus requires developers to be more careful. The issue is that updates are not immediately applied globally, thus the conditions under which they are applied are subject to change, which can easily break data invariants. Many eventually consistent systems address this issue by providing higher-level data types to programmers. However, the semantic details often remain sketchy. Experience has shown that ad-hoc approaches to the semantics and implementation of such systems can lead to surprising or unacceptable behaviors (e.g., an online “shopping cart” where deleted items reappear).
For example, eventual consistency uses a variety of techniques such as general causally-ordered broadcast or pairwise anti-entropy to propagate updates. These techniques are particular implementations that treat visibility as a partial order. As for arbitration order, it has been observed that two general approaches commonly used. The most common approach is to use (logical or actual) timestamps as a simple way to arbitrate events. Another approach (sometimes combined with timestamps) is to make updates commutative, which makes arbitration unnecessary (i.e., an arbitrary serialization of the visibility order can be selected for updates.
In addition, there is a large body of known work on “transactions.” Most academic work in this area considers strong consistency (serializable transactions) only, and is thus not directly applicable to eventual consistency. Nevertheless there are some similarities. For example, one conventional technique provides insight on the limitations of serializable transactions, and proposes workarounds similar to those used by eventual consistency (timestamps and commutative updates). However, transactions remain tentative during disconnection with this technique. Another concept related to transactions considers “snapshot isolation” in relaxing its “consistency model,” but transactions can still fail, and can not commit in the presence of network partitions. Yet another concept considers coarse-grained transactions, and uses abstract data types to facilitate concurrent transactions.
Prior work on “operational transformations” can be understood as a specialized form of eventual consistency where updates are applied to different replicas in different orders, but are themselves modified in such a way as to guarantee convergence. This specialized formulation can provide highly efficient broadcast-based real-time collaboration, but poses significant implementation challenges.